/**
 * @param {number[]} nums
 * @return {number}
 */
//dp法:太慢了
// var jump = function (nums) {
// let n = n
// let dp = new Array(n).fill(Infinity)
// //dp[0]位置不需要跳跃
// dp[0] = 0

// for (let i = 0; i < n; i++) {
//   for (let j = i + 1; j <= i + nums[i]; j++) {
//     dp[j] = Math.min(dp[j], dp[i] + 1)
//   }
// }

// return dp[n - 1]
// };
//贪心
var jump = function (nums) {
  let n = nums.length
  let maxReach = 0//当前能跳到的最远索引(全局)
  let end = 0//当前能跳到的边界(局部一跳)
  let step = 0//步数
  // 不需要看 nums[n-1]: 因为不会再从 n-1 这个索引继续跳，所以只需要循环到 i = n - 2 就可以
  for (let i = 0; i < n - 1; i++) {
    //更新全局索引
    maxReach = Math.max(maxReach, i + nums[i])
    //如果i到达end:更新局部索引为全局索引,步数+1
    if (i === end) {
      end = maxReach
      step++
    }
  }

  //返回跳跃到nums[n-1]的步数
  return step
};